/*
Date:20210602 18:22PM
key:1.首先暴力的话O(n^2)，过不了最后一个测试点。
    2.O(n)的做法涉及前缀和和哈希map 原理是同余定理 当a-b=0(mod k) ,a=b(mod k)
    这个a-b就要通过前缀和实现。
    dp[i]=至i前缀和%k.
    3.然后就带着map<%k的结果,第一次的索引>去遍历dp数组
    没有%k的结果就插入，右就比较一下索引与当前i
    4.注意可以设置前缀和数组大小为nums.size()+1，因为第一个前缀和设置为0(类似哨兵)会方便 前缀和相减操作时 左端点为起点的情况
*/
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) 
    {
        
        //前缀和数组
        int n=nums.size();
        n++;
        int*dp=new int[n];
        dp[0]=0;
        for(int i=1;i<n;i++)
        {
            dp[i]=(dp[i-1]+nums[i-1])%k;
        }
        //mod k结果 第一个索引
        unordered_map<int,int>m;
        for(int i=0;i<n;i++)
        {
            auto g=m.find(dp[i]);
            if(g==m.end())
            {
                m.insert(pair<int,int>(dp[i],i));
            }
            else{if(i-g->second>1){return 1;}}
        }

        return 0;
    }
};